37. 解数独
37. 解数独
Similar Question
Solution Tips
方案一: 回溯
假的二元思路, 本质上还是两个 for 循环
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function(board) {
// 每一行, 每一列, 每一个九宫格都需要单独保存一个数组
// 用来快速判断当前位置有哪些候选项, 这样每填一个格子都得更新三个数组
// 因为只有唯一一个正确答案
const n = board.length;
const rowRestMatrix = new Array(n).fill('').map(() => new Array(n).fill('').map((_, i) => i + 1));
const colRestMatrix = new Array(n).fill('').map(() => new Array(n).fill('').map((_, i) => i + 1));
const nineRestMatrix = new Array(3).fill('').map(() => new Array(3).fill('').map(() => new Array(n).fill('').map((_, i) => i + 1)));
for (let row = 0; row < n; row++) {
for (let col = 0; col < n; col++) {
// 记录剩余可以填入的数字
const item = board[row][col];
if (item !== '.') {
const val = item - 1;
rowRestMatrix[row][val] = 0;
colRestMatrix[col][val] = 0;
const r = Math.floor(row / 3);
const c = Math.floor(col / 3);
nineRestMatrix[r][c][val] = 0;
}
}
}
dfs(0, 0);
return board;
// 回溯的填入, 每次都得更新 3 * 9 个数, 每次更新 3 个数组
// 二元思路可能比较好写, 反正两个 for 循环根本不可能回溯, 复杂度太恐怖了
function dfs(row, col) {
const item = board[row][col];
if (item === '.') {
// 找出可用的数字, 一个个尝试
const rRest = rowRestMatrix[row];
const cRest = colRestMatrix[col];
const r = Math.floor(row / 3);
const c = Math.floor(col / 3);
const nRest = nineRestMatrix[r][c];
for (let i = 0; i < n; i++) {
if (rRest[i] > 0 && cRest[i] > 0 && nRest[i] > 0) {
// 该数字可填入
board[row][col] = i + 1 + '';
// 更新 rest
rRest[i] = -rRest[i];
cRest[i] = -cRest[i];
nRest[i] = -nRest[i];
if (col === 8) {
if (row < 8) {
if (dfs(row + 1, 0)) {
return true;
}
}
else {
// 填完了, 快速退出
return true;
}
}
else {
if (dfs(row, col + 1)) {
return true;
}
}
// 还原 rest
rRest[i] = -rRest[i];
cRest[i] = -cRest[i];
nRest[i] = -nRest[i];
board[row][col] = '.';
}
// 三个值全部等于-1
// else if (rRest[i] <= 0 && cRest[i] <= 0 && nRest[i] <= 0) {
// // 这个格子没有数字可以填充, 说明目前的方案不行, 需要回溯
// return false;
// }
}
// 一整行都填完了,不对
return false;
}
else {
if (col === 8) {
if (row < 8) {
if (dfs(row + 1, 0)) {
return true;
}
}
else {
// 填完了, 快速退出
return true;
}
}
else {
if (dfs(row, col + 1)) {
return true;
}
}
}
}
};
方案一优化: 二维的回溯递归
这一行已经遍历完了, 下一行还是从 col 开始遍历, 所以 col 需要是 0
做了 curRow 和 curCol 的优化, 这里也必须要注意才行, 非常细节的点
var solveSudoku = function(board) {
// 每一行, 每一列, 每一个九宫格都需要单独保存一个数组
// 用来快速判断当前位置有哪些候选项, 这样每填一个格子都得更新三个数组
// 因为只有唯一一个正确答案
// 感觉每次填一个数字说不定还挺不错的? 每次先把能确定的都确定了?
// 犹豫就会败北, 速速行动
// 从出现的最多的数字开始填
const n = board.length;
const rowRestMatrix = new Array(n).fill('').map(() => new Array(n).fill('').map((_, i) => i + 1));
const colRestMatrix = new Array(n).fill('').map(() => new Array(n).fill('').map((_, i) => i + 1));
const nineRestMatrix = new Array(3).fill('').map(() => new Array(3).fill('').map(() => new Array(n).fill('').map((_, i) => i + 1)));
for (let row = 0; row < n; row++) {
for (let col = 0; col < n; col++) {
// 记录剩余可以填入的数字
const item = board[row][col];
if (item !== '.') {
const val = item - 1;
rowRestMatrix[row][val] = 0;
colRestMatrix[col][val] = 0;
const r = Math.floor(row / 3);
const c = Math.floor(col / 3);
nineRestMatrix[r][c][val] = 0;
}
}
}
dfs(0, 0);
return board;
// 回溯的填入, 每次都得更新 3 * 9 个数, 每次更新 3 个数组
// 二元思路可能比较好写, 反正两个 for 循环根本不可能回溯, 复杂度太恐怖了
// 因为有快速退出, 所以两个for循环也没关系, 反而是两个for循环更符合模拟的逻辑
// 与二元思路其实没有关系
function dfs(row, col) {
for (let i = row; i < n; i++) {
for (let j = col; j < n; j++) {
const item = board[i][j];
if (item === '.') {
// 找出可用的数字, 一个个尝试
const rRest = rowRestMatrix[i];
const cRest = colRestMatrix[j];
const r = Math.floor(i / 3);
const c = Math.floor(j / 3);
const nRest = nineRestMatrix[r][c];
for (let k = 0; k < n; k++) {
if (rRest[k] > 0 && cRest[k] > 0 && nRest[k] > 0) {
// 该数字可填入
board[i][j] = k + 1 + '';
// 更新 rest
rRest[k] = -rRest[k];
cRest[k] = -cRest[k];
nRest[k] = -nRest[k];
const newRow = j === 8 ? i + 1 : i;
const newCol = j === 8 ? 0 : j + 1;
if (dfs(newRow, newCol)) {
return true;
}
// 还原 rest
rRest[k] = -rRest[k];
cRest[k] = -cRest[k];
nRest[k] = -nRest[k];
board[i][j] = '.';
}
}
// 一整行都填完了,也找不到合适的数字, 说明这条线路不对
return false;
}
}
// 这一行已经遍历完了, 下一行还是从 col 开始遍历, 所以 col 需要是 0
// 做了 curRow 和 curCol 的优化, 这里也必须要注意才行, 非常细节的点
col = 0;
}
// 所有行的遍历完了, 走到这里肯定满足, 所以与 col 需要重置为 0 不同, 这里是快速退出的点
return true;
}
};
方案一优化: 预处理优化
预处理的数组还可以优化的更移动, 使用 true or false 来标记, 还原的时候也是还原为 true, 取值通过 index 来就可以了
还可以在预处理的时候构造出空格数组, 这样遍历的时候就可以更加快速? 但是感觉会很难搞懂
这种预处理出矩阵中的可操作坐标, 之前也遇到过, 但是当时也是没有当一回事, 觉得太麻烦了
这样的一个好处就是不用考虑 col 的重置, 因为可以直接读取到下一个空格的位置, 每次回溯的时候也不用考虑坐标的边界了, 是更加合理的处理方式
var solveSudoku = function(board) {
// 每一行, 每一列, 每一个九宫格都需要单独保存一个数组
// 用来快速判断当前位置有哪些候选项, 这样每填一个格子都得更新三个数组
// 因为只有唯一一个正确答案
// 感觉每次填一个数字说不定还挺不错的? 每次先把能确定的都确定了?
// 犹豫就会败北, 速速行动
// 从出现的最多的数字开始填
const n = board.length;
const rowRestMatrix = Array.from(
{ length: 9 },
() => Array.from({ length: 9 }).fill(true)
)
const colRestMatrix = Array.from(
{ length: 9 },
() => Array.from({ length: 9 }).fill(true)
)
const nineRestMatrix = Array.from(
{ length: 3 },
() => Array.from(
{ length: 3 },
() => Array.from({ length: 9 }).fill(true)
)
)
// 存储所有的空格, 遍历的时候就不用考虑 for 循环以及 row col 的边界重置情况了
const space = [];
for (let row = 0; row < n; row++) {
for (let col = 0; col < n; col++) {
// 记录剩余可以填入的数字
const item = board[row][col];
const val = item - 1;
if (item !== '.') {
// 这里的逻辑太绕了... true 代表着当前值不可用...
// 所以需要做一层翻转, 默认填充 true ,这里置为 false 表明不可用
rowRestMatrix[row][val] = false;
colRestMatrix[col][val] = false;
const r = Math.floor(row / 3);
const c = Math.floor(col / 3);
nineRestMatrix[r][c][val] = false;
}
else {
space.push([row, col])
}
}
}
dfs(0);
return board;
// 回溯的填入, 每次都得更新 3 * 9 个数, 每次更新 3 个数组
// 二元思路可能比较好写, 反正两个 for 循环根本不可能回溯, 复杂度太恐怖了
// 因为有快速退出, 所以两个for循环也没关系, 反而是两个for循环更符合模拟的逻辑
// 与二元思路其实没有关系
function dfs(pos) {
if (pos > space.length - 1) {
// 遍历完了, 快速结束
return true;
}
const [i, j] = space[pos];
const item = board[i][j];
if (item === '.') {
// 找出可用的数字, 一个个尝试
const rRest = rowRestMatrix[i];
const cRest = colRestMatrix[j];
const r = Math.floor(i / 3);
const c = Math.floor(j / 3);
const nRest = nineRestMatrix[r][c];
for (let k = 0; k < n; k++) {
if (rRest[k] && cRest[k] && nRest[k]) {
// 该数字可填入
board[i][j] = k + 1 + '';
// 更新 rest
rRest[k] = cRest[k] = nRest[k] = false;
if (dfs(pos + 1)) {
return true;
}
// 还原 rest
rRest[k] = cRest[k] = nRest[k] = true;
board[i][j] = '.';
}
}
// 一整行都填完了,也找不到合适的数字, 说明这条线路不对
return false;
}
}
};